package leetcode.code1305;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.tree.TreeNode;

public class Solution implements IDebug {

	public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
		List<Integer> list1 = new ArrayList<>();
		List<Integer> list2 = new ArrayList<>();
		sort(root1, list1);
		sort(root2, list2);
		List<Integer> ans = merge(list1, list2);
		return ans;
	}

	private List<Integer> merge(List<Integer> list1, List<Integer> list2) {
		int len1 = list1.size();
		int len2 = list2.size();
		int p1 = 0, p2 = 0;
		List<Integer> ans = new ArrayList<>();
		while (p1 < len1 && p2 < len2) {
			int num1 = list1.get(p1);
			int num2 = list2.get(p2);
			if (num1 <= num2) {
				ans.add(num1);
				p1++;
			} else {
				ans.add(num2);
				p2++;
			}
		}
		while (p1 < len1) {
			int num1 = list1.get(p1);
			ans.add(num1);
			p1++;
		}
		while (p2 < len2) {
			int num2 = list2.get(p2);
			ans.add(num2);
			p2++;
		}
		return ans;
	}

	private void sort(TreeNode root1, List<Integer> list1) {
		if (root1 == null) {
			return;
		}
		this.sort(root1.left, list1);
		list1.add(root1.val);
		this.sort(root1.right, list1);
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
